/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package routefinder.algorithm;

import routefinder.*;
import routefinder.exception.RouteFinderException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.logging.Logger;

public class MyBFSTrips {

    /**
     * The graph.
     */
    private final IRoutesMap map;
    /**
     * The set of cities for which the shortest distance to the source
     * has been found.
     */
    private final Set<City> settledNodes = new HashSet<City>();
    /**
     * Accumulates the amount of possible trips from the starting city to the destination.
     */
    private int trips;
    /**
     * keeps track of the destination node, so we know when something funny happened.
     */
    private City destinationNode;
    private boolean isStrictNumberOfStops = false;
    /**
     * keeps track of the source node, so we know when something funny happened.
     */
    private City sourceNode;
    private final Queue<City> unsettledNodes = new LinkedList<City>();
    // the maximum distance of a route
    private int maximumNumberOfStops = Integer.MAX_VALUE;

    public MyBFSTrips(IRoutesMap map) {
        if (map == null) {
            throw new RouteFinderException("A map must be supplied");
        }
        this.map = map;
    }

    /**
     * Initialize all data structures used by the algorithm.
     *
     * @param start the source node
     */
    private void init(City start, City destination,int maximumDistance, boolean isStrictNumberOfStops) {
        this.maximumNumberOfStops = maximumDistance;
        this.isStrictNumberOfStops = isStrictNumberOfStops;
        sourceNode = start;
        destinationNode = destination;
        unsettledNodes.clear();
        unsettledNodes.offer(start);
        settledNodes.clear();
        trips = 0;
    }

    public int execute(City start, City destination,int maximumDistance, boolean isStrictDistance) {
        Logger.getLogger(Dijkstra.class.getName()).info("Executing BFS on: " + start + " " + destination);
        init(start, destination, maximumDistance, isStrictDistance);
        bfs("", 0, null);
        return trips;
    }

    private void bfs(String routePath, int cost, City previousNode) {
        if (cost > maximumNumberOfStops) {
            return;
        }

        if (isStrictNumberOfStops) {
            if (cost == maximumNumberOfStops && routePath.endsWith(destinationNode.getName())) { //TODO use Route
                Logger.getLogger(MyBFSTrips.class.getName()).info(routePath + ", " + cost);
                trips++;
            }
        } else {
            if (cost <= maximumNumberOfStops && routePath.endsWith(destinationNode.getName())) { //TODO use Route
                Logger.getLogger(MyBFSTrips.class.getName()).info(routePath + ", " + cost);
                trips++;
            }
        }

        if (previousNode == null) {
            previousNode = sourceNode;
        }

        // visit neighbors
        for (Link v : map.getDestinations(previousNode)) {
            int newCost = cost + 1;
            if (newCost > 0) {
                bfs(routePath + v.getCity().getName(), newCost, v.getCity());
            }
        }
    }
}
